package org.lql.algo.codecrush.hot100.graphTheory;

/**
 * @author: liangqinglong
 * @date: 2025-09-16 00:19
 * @description: 200. 岛屿数量 <a href="https://leetcode.cn/problems/number-of-islands/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class NumIslands {

	// 每个点是否访问过
	private boolean[][] visited;
	// 地图方向数组
	private static int[][] directions;
	// 网格横纵数量
	int m;
	int n;

	public int numIslands(char[][] grid) {
		m = grid.length;
		n = grid[0].length;
		visited = new boolean[m][n];
		directions = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
		int ans = 0;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				// 从没访问过的岛屿开始
				if (grid[i][j] == '1' && !visited[i][j]) {
					ans++;
					dfs(grid, i, j);
				}
			}
		}
		return ans;
	}

	public void dfs(char[][] grid, int sx, int sy) {
		visited[sx][sy] = true;
		for (int[] direction : directions) {
			int nx = sx + direction[0];
			int ny = sy + direction[1];
			// 边界判断
			if (nx < 0 || nx >= m || ny < 0 || ny >= n) {
				continue;
			}
			// 访问过或者不是陆地
			if (visited[nx][ny] || grid[nx][ny] == '0') {
				continue;
			}
			dfs(grid, nx, ny);
		}
	}

	public static void main(String[] args) {
		char[][] grid = new char[][]{
				{'1', '1', '1', '1', '0'},
				{'1', '1', '0', '1', '0'},
				{'1', '1', '0', '0', '0'},
				{'0', '0', '0', '1', '0'}
		};
		NumIslands numIslands = new NumIslands();
		System.out.println(numIslands.numIslands(grid));
	}
}
